package com.acwing.partition2;

import java.io.*;
import java.util.*;

/**
 * @author `RKC`
 * @date 2021/12/29 9:24
 */
@SuppressWarnings("all")
public class AC190字串变换 {

    private static final int P = 13331;
    //规则可能出现一对多的问题，因此使用List，并分别创建一个正向规则和一个反向规则的映射
    private static final Map<Long, List<String>> originRules = new HashMap<>(6);
    private static final Map<Long, List<String>> destRules = new HashMap<>(6);

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        String a = s[0], b = s[1];
        while (true) {
            String str = reader.readLine();
            if (str == null || str.length() == 0) break;
            s = str.split("\\s+");
            //正向创建规则
            long h = hash(s[0]);
            List<String> ruleList = originRules.getOrDefault(h, new ArrayList<>());
            ruleList.add(s[1]);
            originRules.put(h, ruleList);
            //反向创建规则
            h = hash(s[1]);
            ruleList = destRules.getOrDefault(h, new ArrayList<>());
            ruleList.add(s[0]);
            destRules.put(h, ruleList);
        }
        int ans = bfs(a, b);
        if (ans > 10) writer.write("NO ANSWER!\n");
        else writer.write(ans + "\n");
        writer.flush();
    }

    private static int bfs(String a, String b) {
        if (a.equals(b)) return 0;
        Map<String, Integer> originMap = new HashMap<>(), destMap = new HashMap<>();
        originMap.put(a, 0);
        destMap.put(b, 0);
        Queue<String> originQue = new LinkedList<>(), destQue = new LinkedList<>();
        originQue.add(a);
        destQue.add(b);
        while (!originQue.isEmpty() && !destQue.isEmpty()) {
            int answer = originQue.size() <= destQue.size() ? search(originQue, originMap, originRules, destMap)
                    : search(destQue, destMap, destRules, originMap);
            if (answer <= 10) return answer;
        }
        return 11;
    }

    private static int search(Queue<String> originQue, Map<String, Integer> originMap, Map<Long, List<String>> rules, Map<String, Integer> destMap) {
        String curr = originQue.poll();
        StringHash hash = new StringHash(curr);
        int step = originMap.get(curr);
        for (int i = 1; i <= curr.length(); i++) {
            for (int j = i; j <= curr.length(); j++) {
                //得到区间[i,j)的哈希，并检查规则中是否有匹配的字符串
                long h = hash.substringHash(i, j);
                if (!rules.containsKey(h)) continue;
                for (String s : rules.get(h)) {
                    //有存在的匹配规则，将映射后的字符串替换到当前字符（需要拷贝一份）上去
                    String next = replace(curr, s, i - 1, j);
                    if (destMap.containsKey(next)) return destMap.get(next) + step + 1;
                    if (originMap.containsKey(next)) continue;
                    originMap.put(next, step + 1);
                    originQue.add(next);
                }
            }
        }
        return 11;
    }

    private static String replace(String str, String s, int start, int end) {
        //直接利用StringBuilder来帮我们替换，另外String家族都是左闭右开
        StringBuilder sb = new StringBuilder(str);
        sb.replace(start, end, s);
        return sb.toString();
    }

    private static class StringHash {
        private long[] prefix;
        private long[] hash;
        private String s;

        public StringHash(String s) {
            this.s = s;
            prefix = new long[s.length() + 1];
            hash = new long[s.length() + 1];
            prefix[0] = 1;
            for (int i = 1; i <= s.length(); i++) {
                prefix[i] = prefix[i - 1] * P;
                hash[i] = hash[i - 1] * P + s.charAt(i - 1);
            }
        }

        public long substringHash(int x, int y) {
            return hash[y] - hash[x - 1] * prefix[y - x + 1];
        }

        public long get() { return hash[s.length()]; }
    }

    private static long hash(String s) {
        long[] p = new long[s.length() + 1], h = new long[s.length() + 1];
        p[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + s.charAt(i - 1);
        }
        return h[s.length()];
    }
}
